/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class PalindromicSubstrings {
	public int countSubstrings(String s) {
		int n = s.length();
		boolean dp[][] = new boolean[n][n];
		int sum = 0;
		for (int i = n - 1; i >= 0; i--) {
			dp[i][i] = true;
			if (i < n - 1 && s.charAt(i + 1) == s.charAt(i)) {
				dp[i][i + 1] = true;
				sum++;
			}
			sum++;
			for (int j = i + 2; j < n; j++) {
				if ((dp[i + 1][j - 1]) && s.charAt(i) == s.charAt(j)) {
					dp[i][j] = true;
					sum++;
				}
			}
		}
		return sum;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(new PalindromicSubstrings().countSubstrings("aaa"));
	}

}
